class Solution {
public:
    int movingCount(int threshold, int rows, int cols)
    {
        cnt = 0;
        this->rows = rows;
        this->cols = cols;
        this->threshold = threshold;
        int path[rows*cols];
        for(int i = 0 ; i < rows*cols ;++i)
    		path[i] = 0;
        moveCore(0,0,path);
        return cnt;
    }

    void moveCore(int x,int y,int path[])
    {
    	if(x < cols && y < rows && !path[cols * y + x] && legal(x,y))
    	{
    		++cnt;
    		path[cols * y + x] = 1;
    		moveCore(x+1,y,path);
    		moveCore(x,y+1,path);
    	}
    }
    bool legal(int x,int y)
    {
    	int sum = 0 ;
    	while(x)
    	{
    		sum += x%10;
    		x/=10;
    	}
    	while(y)
    	{
    		sum+= y%10;
    		y/=10;
    	}
    	return sum <= threshold ?true:false;
    }

private:
	int threshold;
	int cnt;
	int rows;
	int cols;
};